from typing import List


class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        # 移除左右多余的括号
        s = s.lstrip(")").rstrip("(")
        size = len(s)

        # 统计必须删除的左括号数量
        delete_left_num = delete_right_num = 0
        for ch in s:
            if ch == "(":
                delete_left_num += 1
            elif ch == ")":
                delete_left_num = max(delete_left_num - 1, 0)
        for ch in s[::-1]:
            if ch == ")":
                delete_right_num += 1
            elif ch == "(":
                delete_right_num = max(delete_right_num - 1, 0)
        # print(s, ":", delete_left_num, delete_right_num)

        # 深度优先搜索
        ans = set()

        def dfs(i, ss, now, delete_left, delete_right):
            # 处理已经寻找到字符串末尾的情况
            if i == size:
                if now == 0:
                    ans.add(ss)

            # 处理尚未寻找到字符串末尾的情况
            else:
                if s[i] == "(":
                    if now == 0:
                        dfs(i + 1, ss + "(", 1, delete_left, delete_right)
                        if delete_left < delete_left_num:
                            dfs(i + 1, ss, now, delete_left + 1, delete_right)
                    elif now > 0:
                        dfs(i + 1, ss + "(", now + 1, delete_left, delete_right)
                        if delete_left < delete_left_num:
                            dfs(i + 1, ss, now, delete_left + 1, delete_right)
                    else:
                        return
                elif s[i] == ")":
                    if now == 0:
                        if delete_right < delete_right_num:
                            dfs(i + 1, ss, now, delete_left, delete_right + 1)
                    elif now > 0:
                        dfs(i + 1, ss + ")", now - 1, delete_left, delete_right)
                        if delete_right < delete_right_num:
                            dfs(i + 1, ss, now, delete_left, delete_right + 1)
                    else:
                        return
                else:
                    dfs(i + 1, ss + s[i], now, delete_left, delete_right)

        dfs(0, "", 0, 0, 0)

        return list(ans)


if __name__ == "__main__":
    # ["()()()", "(())()"]
    print(Solution().removeInvalidParentheses("()())()"))

    # ["(a)()()", "(a())()"]
    print(Solution().removeInvalidParentheses("(a)())()"))

    # [""]
    print(Solution().removeInvalidParentheses(")("))

    # 自制用例 ["()()"]
    print(Solution().removeInvalidParentheses("()))((()"))

    # 测试用例102: ["f"]
    print(Solution().removeInvalidParentheses(")(f"))
